package JZ_Offer.algorithm.other.贪心;

/**
 * 给你一根长度为n的绳子，请把绳子剪成整数长的m段（m、n都是整数，n>1并且m>1），每段绳子的长度记为k[0],k[1],...,k[m]。
 * 请问k[0]xk[1]x...xk[m]可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。
 * 输入一个数n，意义见题面。 输入8 输出18
 * <p>
 * 数据范围：2 ≤ n ≤ 60
 */
public class JZ14_剪绳子 {

    /**
     * 贪心算法就是把所有情况都走一遍
     */
    public int cutRope(int target) {
        int sum = 0;
        for (int i = 1; i < target; i++) {
            int count = count(i, target);
            if (count <= sum) {
                break;
            }
            sum = count;
        }
        return sum;
    }

    /**
     * 统计不同分布时的乘积
     */
    private int count(int step, int target) {
        int sum = 1;
        while (target > 0) {
            if (target - step >= 0) {
                sum *= step;
            } else {
                sum *= target;
            }
            target = target - step;
        }
        return sum;
    }

    public static void main(String[] args) {
        JZ14_剪绳子 main = new JZ14_剪绳子();
        System.out.println(main.cutRope(2));
        System.out.println(main.cutRope(3));
        System.out.println(main.cutRope(4));
        System.out.println(main.cutRope(5));
        System.out.println(main.cutRope(6));
        System.out.println(main.cutRope(7));
        System.out.println(main.cutRope(8));
        System.out.println(main.cutRope(9));
    }
}
